package com.leetcodehot.problems;

public class problems1373 {
    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {
        }

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

    /**
     * 要找最大键值和，且还得满足是二叉搜索树的前提。
     * 一、是否每一个节点都得判断是否是二叉搜索树？->后序遍历其实更合适，左如果不是 那当前节点也就不需要判断
     * 右 同理， 然后往上推
     * 二、
     */
    private int ans = 0;

    // 返回当前root是否是二叉搜索树
    private int[] isBST(TreeNode root) {
        if (root == null)
            return new int[]{
                    // 使得父节点一定满足
                    Integer.MAX_VALUE, Integer.MIN_VALUE, 0};
        int[] left = isBST(root.left);
        int[] right = isBST(root.right);
        int x = root.val;
        if (x <= left[1] || x >= right[0]) {
            return new int[]{
                    // 使得父节点一定不满足
                    Integer.MIN_VALUE, Integer.MAX_VALUE, 0};
        }
        int s = left[2] + right[2] + x;
        ans = Math.max(ans, s);
        return new int[]{Math.min(left[0], x), Math.max(right[1], x), s};
    }

    public int maxSumBST(TreeNode root) {
        isBST(root);
        return ans;
    }
}
